import common.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 236. Lowest Common Ancestor Of A Binary Tree 二叉树的最近公共祖先
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 */
class LowestCommonAncestorOfABinaryTree {

    /**
     *     方法：递归查找最近公共祖先
     *
     *     Args:
     *         root: 二叉树的根节点
     *         p: 第一个目标节点
     *         q: 第二个目标节点
     *
     *     Returns:
     *         TreeNode: p和q的最近公共祖先节点
     *
     *     Time: O(n)，其中n是二叉树中的节点数，最坏情况下需要遍历整棵树
     *
     *     Space: O(h)，其中h是二叉树的高度，递归调用栈的空间
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){
            return root;
        }
        return left != null? left : right;
    }

    /**
     *     方法：lowestCommonAncestor1 使用父指针查找最近公共祖先
     *
     *     通过DFS构建每个节点到其父节点的映射，然后从p节点开始向上遍历并记录访问过的节点。
     *     接着从q节点开始向上遍历，第一个在p的路径中出现的节点即为最近公共祖先。
     *
     *     Args:
     *         root: 二叉树的根节点
     *         p: 第一个目标节点
     *         q: 第二个目标节点
     *
     *     Returns:
     *         TreeNode: p和q的最近公共祖先节点
     *
     *     Time: O(n)，其中n是二叉树中的节点数，需要遍历整棵树构建父指针映射
     *
     *     Space: O(n)，存储父指针映射和访问记录需要O(n)的空间
     */
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while(p != null){
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while(q != null){
            if(visited.contains(q.val)){
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

    private void dfs(TreeNode root){
        if(root.left != null){
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if(root.right != null){
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
}